package lib

//link to 10
//*可以匹配0或任意个字符
func init() {
	Probs = append(Probs, Problem{
		Num:         44,
		Discription: "通配符匹配",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func IsMatch(s string, p string) bool {
	m := len(s)
	n := len(p)
	//dp[i][j]代表s[:i]和p[:j]是否匹配
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	//考虑p开头就是'*'的情况，因为'*'可以匹配0或任意多个字符，注意边界
	for j := 1; j <= n; j++ {
		dp[0][j] = dp[0][j-1] && p[j-1] == '*'
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '?' {
				dp[i][j] = dp[i-1][j-1]
				continue
			}

			if p[j-1] == '*' {
				for k := i; k >= 0; k-- {
					if dp[k][j-1] {
						dp[i][j] = true
						break
					}
				}
				continue
			}

			dp[i][j] = s[i-1] == p[j-1] && dp[i-1][j-1]
		}
	}

	return dp[m][n]
}
